package org.review.datastructure;

import java.util.Stack;

public class BinaryTree {
    public static void main(String[] args) {
        Node root = new Node(1, "根节点");
        Node nodeL = new Node(2, "二级左");
        Node nodeR = new Node(3, "二级右");

        Node node3L = new Node(4, "3级左");
        Node node3R = new Node(5, "3级右");

        nodeL.setLeft(node3L);
        nodeL.setRight(node3R);

        root.setLeft(nodeL);
        root.setRight(nodeR);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(root);
        binaryTree.delNode(5);
        binaryTree.preOrder();

    }

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //    二叉树前序遍历的方式进行遍历
    public void sequenceArr(int[] arr) {
        for (int i = 0; i < arr.length; i = (i * 2) + 1) {

        }
    }


    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
                return;
            }

            root.delNode(no);
        }
    }

    public void preOrder() {
        if (root != null) {
            this.root.preOrder();
        }
    }

    public void inorder() {
        if (root != null) {
            root.inorder();
        }
    }

    public void postOrder() {
        if (root != null) {
            root.postOrder();
        }
    }


    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preSearch(no);
        }
        return null;
    }

    public Node inOrderSearch(int no) {
        if (root != null) {
            return root.inSearch(no);
        }
        return null;
    }

    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postSearch(no);
        }
        return null;
    }


}

class Node {
    private int no;
    private String name;

    private Node left;
    private Node right;


    //    删除节点， 如果是子树 就移除，如果是叶子节点就删除并退出递归
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }

        if (this.right != null) {
            this.right.delNode(no);
        }
    }


    //    前序查找
    public Node preSearch(int no) {
        if (this.no == no) {
            return this;
        }
        if (this.left != null) {
            Node node = this.left.preSearch(no);
            if (node != null) {
                return node;
            }
        }
        if (this.right != null) {
            return this.right.preSearch(no);
        }
        return null;
    }

    //中序查找
    public Node inSearch(int no) {
        if (this.left != null) {
            Node node = this.left.inSearch(no);
            if (node != null) {
                return node;
            }
        }
        if (this.no == no) return this;
        if (this.right != null) {
            return this.right.inSearch(no);
        }
        return null;
    }

    //    后续查找
    public Node postSearch(int no) {
        if (this.left != null) {
            Node node = this.left.postSearch(no);
            if (node != null) {
                return node;
            }
        }

        if (this.right != null) {
            Node node = this.right.postSearch(no);
            if (node != null) {
                return node;
            }
        }
        if (this.no == no) {
            return this;
        }
        return null;

    }

    public Node preSearchStack(int no) {
        Stack<Node> nodes = new Stack<>();
        nodes.push(this);
        while (!nodes.isEmpty()) {
            Node pop = nodes.pop();
            if (pop.no == no) {
                return pop;
            }

            if (pop.right != null) {
                nodes.push(pop.right);
            }

            if (pop.left != null) {
                nodes.push(pop.left);
            }
        }
        return null;
    }


    // 前序   父节点 然后左 右
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void inorder() {
        if (this.left != null) this.left.inorder();
        System.out.println(this);
        if (this.right != null) this.right.inorder();
    }

    //    后续遍历
    public void postOrder() {
        if (this.left != null) this.left.postOrder();
        if (this.right != null) this.right.postOrder();
        System.out.println(this);
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }


    @Override
    public String toString() {
        return "Node{" + "no=" + no + ", name='" + name + '\'' + '}';
    }
}
